By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 28, Issue 2, pp. 383-769

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

A Downward Collapse within the Polynomial Hierarchy

Edith Hemaspaandra, Lane A. Hemaspaandra, and Harald Hempel

pp. 383-393

BibTeX  Abstract Full Text:  PDF

Genericity, Randomness, and Polynomial-Time Approximations

Yongge Wang

pp. 394-408

BibTeX  Abstract Full Text:  PDF

Universal Limit Laws for Depths in Random Trees

Luc Devroye

pp. 409-432

BibTeX  Abstract Full Text:  PDF

Average-Case Lower Bounds for Noisy Boolean Decision Trees

William Evans and Nicholas Pippenger

pp. 433-446

BibTeX  Abstract Full Text:  PDF

Competitive Algorithms for Layered Graph Traversal

Amos Fiat, Dean P. Foster, Howard Karloff, Yuval Rabani, Yiftach Ravid, and Sundar Vishwanathan

pp. 447-462

BibTeX  Abstract Full Text:  PDF

On Multirate Rearrangeable Clos Networks

D. Z. Du, B. Gao, F. K. Hwang, and J. H. Kim

pp. 463-470

BibTeX  Abstract Full Text:  PDF

Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time

Francis Chin and Cao An Wang

pp. 471-486

BibTeX  Abstract Full Text:  PDF

Reconstructing Algebraic Functions from Mixed Data

Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, and Madhu Sudan

pp. 487-510

BibTeX  Abstract Full Text:  PDF

Optimal Broadcast with Partial Knowledge

Baruch Awerbuch, Israel Cidon, Shay Kutten, Yishay Mansour, and David Peleg

pp. 511-524

BibTeX  Abstract Full Text:  PDF

Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs

Sridhar Rajagopalan and Vijay V. Vazirani

pp. 525-540

BibTeX  Abstract Full Text:  PDF

Optimal Construction of Edge-Disjoint Paths in Random Graphs

Andrei Z. Broder, Alan M. Frieze, Stephen Suen, and Eli Upfal

pp. 541-573

BibTeX  Abstract Full Text:  PDF

Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps

Zoran Ivkovic and Errol L. Lloyd

pp. 574-611

BibTeX  Abstract Full Text:  PDF

Dynamic Trees and Dynamic Point Location

Michael T. Goodrich and Roberto Tamassia

pp. 612-636

BibTeX  Abstract Full Text:  PDF

Query Order

Lane A. Hemaspaandra, Harald Hempel, and Gerd Wechsung

pp. 637-651

BibTeX  Abstract Full Text:  PDF

Finding the k Shortest Paths

David Eppstein

pp. 652-673

BibTeX  Abstract Full Text:  PDF

Exact Learning of Discretized Geometric Concepts

Nader H. Bshouty, Paul W. Goldberg, Sally A. Goldman, and H. David Mathias

pp. 674-699

BibTeX  Abstract Full Text:  PDF

Fast Exponentiation Using Data Compression

Yacov Yacobi

pp. 700-703

BibTeX  Abstract Full Text:  PDF

A Polynomial Time Complexity Bound for Computations on Curves

P. G. Walsh

pp. 704-708

BibTeX  Abstract Full Text:  PDF

Stochastic Contention Resolution With Short Delays

Prabhakar Raghavan and Eli Upfal

pp. 709-719

BibTeX  Abstract Full Text:  PDF

Asymptotically Optimal Election on Weighted Rings

Lisa Higham and Teresa Przytycka

pp. 720-732

BibTeX  Abstract Full Text:  PDF

The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms

Phillip B. Gibbons, Yossi Matias, and Vijaya Ramachandran

pp. 733-769

BibTeX  Abstract Full Text:  PDF